package cxydmmszl.chapter08.t140;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 数组排序之后相邻数的最大差值
 * <li style="color: red;">Desc</li>
 * 给定一个整形数组arr，返回排序后相邻两数的最大差值<br/><br/>
 * <li style="color: red;">Link</li> CD40
 *
 * @author habitplus
 * @since 2021-09-07 14:33
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];
        String[] ss;
        ss = bf.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }
        bf.close();

        int ans = maxGap(arr);
        System.out.println(ans);
    }

    private static int maxGap(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }

        /*
            桶排序过程
         */
        int n = arr.length;
        // 1. 求最大值与最小值
        int minNum = Integer.MAX_VALUE;
        int maxNum = Integer.MIN_VALUE;
        for (int e : arr) {
            minNum = Math.min(minNum, e);
            maxNum = Math.max(maxNum, e);
        }

        if (minNum == maxNum) return 0;

        // 2. 将所有的数（最大值和最小值）放进桶内
        // 每个桶只记录桶内的最大值 bucket[i][0] 和 最小值 bucket[i][1]
//        int[][] bucket = new int[n + 1][2];
        int[] bucketMaxs = new int[n + 1];
        int[] bucketMins = new int[n + 1];
        // 标记桶内是否有数
        boolean[] hasNum = new boolean[n + 1];
        int bid;
        for (int num : arr) {
            // 计算桶号
            bid = getBucketId(num, n, minNum, maxNum);
            bucketMaxs[bid] = hasNum[bid] ? Math.max(num, bucketMaxs[bid]) : num;
            bucketMins[bid] = hasNum[bid] ? Math.min(num, bucketMins[bid]) : num;
            hasNum[bid] = true;
        }

        // 3. 计算相邻的两个桶的差值，取最大的那个
        int ans = 0;
        int lastMax = bucketMaxs[0]; // 初始设为第一个桶中的最大值
        for (int i = 1; i <= n; i++) {
            if (hasNum[i]) {
                // 当前桶内有数
                ans = Math.max(ans, bucketMins[i] - lastMax);
                lastMax = bucketMaxs[i];
            }
        }

        return ans;
    }

    // 使用 long 是为了防止乘法溢出
    private static int getBucketId(long num, long n, long minNum, long maxNum) {
        return (int) ((num - minNum) * n / (maxNum - minNum));
    }
}
